Este problema es importante en dos aspectos, por el lado teórico, el AEMSRC pertenece al conjunto de problemas definidos como NP-Completos, por lo que dado su complejidad es importante encontrar técnicas heurísticas que encuentren soluciones aceptables en tiempos adecuados; ya que las técnicas determínisticas tienen un comportamiento exponencial.
Por el lado práctico, problemas como encontrar la configuración
óptima de diferentes tipos de redes -de cómputo, carreteras,
etc- tanto en costo como en capacidad de flujo, pueden ser resueltos con
el uso de los algoritmos para el AEMSRC.
Dentro de las técnicas determinísticas propuestas -branch and bound, adaptaciones de los algoritmos de Prim, Kruskal, etc- se consigue obtener la solución óptima global.
De hecho, en redes pequeñas tales algoritmos son muy aceptales
ya que en general estos son eficientes. Sin embargo, por las características
del espacio de búsqueda del problema -nn-2-, en redes
grandes -100 nodos por ejemplo- tales técnicas resultan inaceptables
ya que el crecimiento del tiempo de búsqueda es exponencial.
Las características de las técnicas heurísticas es que son en general rápidas, lo que se observa mejor con tamaños de problemas grandes. Pero por otra parte, no aseguran que puedan encontrar la solución óptima global -no exisitiendo nada que impida encontrarla-, si no que en general encuentran soluciones cercanas a ésta.
En la presente tesis, la técnica heurística propuesta es Algoritmos Genéticos -AG- ya que en general se espera que, por su misma naturaleza los AG y sus operadores tengan un buen comportamiento en este problema -por la experiencia que se ha tenido en problemas semejantes-.